COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	PROBLEMS ASSOCIATED WITH THE 1975 STANFORD AI QUAL 
C00016 ENDMK
C⊗;
PROBLEMS ASSOCIATED WITH THE 1975 STANFORD AI QUAL 
____________________________________________________________________________



To the candidates:

Select one (and only ONE) of the following problems. 
It should NOT be in your area of A.I. specialization.
Notify us of your choice (DBL@SAIL, TW@SAIL, Pat Jacobs at Polya Hall,
Terry Winograd at AI Lab,  Doug Lenat at 497-1391).
Spend a few days on the problem (about 10 hours altogether); work individually.
Then return a copy of your work (to Winograd at the AI Lab). Bear in mind that
there is no "right" answer to any of these problems; your committee will look
over your work and will therefore have some common ground to start the discussion
at the oral itself.  The problems will not be graded. Although there is no
"deadline", please return this as soon as possible, to ensure that all your 
committee members will have read it.   We suggest that you keep a copy for
yourself, to refresh your memory just before the date of your exam.
We also suggest that you don't pick the "easiest" problem: remember that
the main purpose is to give you something to talk about at your oral.
The final assignment of your committee, date, and time of oral should be
available around May 19; the schedule (or a pointer to it) will be posted in
Polya and in the A.I. Lab and in Serra House.  Good luck!



1. Read: Pohl (3rd IJCAI, p. 12) and Harris (p. 23).

(i) Pohl doesn't distinguish between time exhaustion and space exhaustion kinds
    of Type-1 catastrophes, but hints that there might be some things to say
    about them. Can you think of anything?
    How can their frequency be minimized by more careful planning while a system
	is being designed?
    What are some ways one might detect an immenent collapse?
    Once detected, how could its impact be minimized? 

(ii) Propose a simple problem which might lead to an unending search unless
	Pohl's dynamic weighting scheme is used. Could Harris' bandwidth
	constraint solve this problem as well?

(iii) Harris and Pohl both use the Travelling Salesman problem to illustrate
	their techniques. Why is this an apt choice? Does it facilitate comparing
	the two techniques? (warning: if it does, then compare them!)

(iv) Given a resolution theorem-prover, might these techniques be applied
	to advantage?



2. Read: Bledsoe (3rd IJCAI, p. 56)

The system described is dealing with a domain (topology) but does not
seem to possess much knowledge in a format suited to that domain. For
example, humans rely on visual intuitions about space and continuity
quite frequently while attempting proofs in this field. How might
analogical models (like Gelernter's, or Bundy's[3rd IJCAI, p. 130])
be employed by the system? 
In 1973, Bledsoe seemed to expect his system to prove new topology
theorems any day. If today, two years later, this isn't so, how can
you account for this?  That is, how could it be that a system was
able to prove hard but known theorems, yet not a single "new"
interesting one? 


  
3. Read: Woods (3rd IJCAI, p. 200) and a HEARSAY article.

Describe how incremental simulation might have been effectively
employed for some non-speech projects (e.g., the Dendral task, a
large theorem-prover, etc.) Why are so many different experts used in
Woods' project?  How do these experts correspond to the modules in
HEARSAY (Reddy et al; 3rd IJCAI p. 185, p.194)?  How might you
organize an incremental simulation of a system to maintain and draw
inferences from Conceptual Dependency nets (Schank, 3rd IJCAI, p.
255)?  To what extent has the basic idea permeated AI research?
Consider, for example, the "pre-processed" format for input assumed
by Winston's ARCH-learning system.  Is incremental simulation
meaningful for an individual doing research?  Is there a "flaw" in
the idea; can you think of a situation where it might be detrimental
to a final project? 



4. Read: Darlington and Burstall (3rd IJCAI, p. 479), and Boyer and Moore (p. 486).

Could Boyer and Moore's system be programmed using the transformation
schemata concept of Darlington and Burstall? Write one schema for a
particular induction problem (e.g., proving that APPEND is
associative), and indicate how it would be applied.  Is this feasable
for the entire range of Boyer and Moore's system's abilities?
Consider how one might automate the acquisition of new program
transformation schemata (consider, e.g., how META-Dendral automates
rule acquisition for Dendral; see, e.g., Buchanan, 3rd IJCAI, p. 67;
or Buchanan et al. in the references list). 



5. Read about Waltz's work; also, look at Stefanuk (3rd IJCAI, p.612)

Stefanuk and others seem to argue for the use of local processing to
solve problems.  Give a few examples where this is essential, and a
few where only a global attack can get anywhere easily. How might one
characterize the class of problems which need a particular level of
scrutiny?  How does this mirror the problem of using semantic vs
syntactic knowledge? 

Draw an analogy between local/global knowledge and the use of
phonetic/semantic knowledge in speech systems.  Consider how a
successful speech system uses the different levels of knowledge
synergetically (e.g., HEARSAY). Using your analogy, how might one
intermix local and global kinds of knowledge of the kind used by
Waltz? That is, use your analogy to propose a new design for Waltz's
system. 



6.  Sketch out a program to play tic-tac-toe in one of the AI languages
(micro-planner, conniver, QA4).  This is NOT a programming problem.
You are not expected to run the program.  What is important is a discussion
of the basic representations you use and the tradeoffs involved in the
way the program is designed.  In particular discuss how your design
would differ if the program were for 3-D 4x4 tic-tac-toe.



7.  The first paper in 3IJCAI describes a method for searching
"additive and/or graphs".  Find some real AI search problem (where
"real" means in a specific problem domain like game playing,
syntactic parsing, scene analysis, etc.) to which this approach might
be applied.  Discuss why the algorithm would be useful, and the
tradeoffs involved in the different choices (like top-down vs.
bottom-up).  If you can find two domains with different
characteristics, all the better. 



8.  There is a paper by Koffman & Blount in 3IJCAI called "Artificial
Intelligence and Automatic Programming in CAI" (pp. 86-94).  Assume
you wanted to write a program which would take the role of the
STUDENT (i.e. the other participant in a dialog with their program.)
Discuss the basic issues you would need to handle, and the ways in
which your result would be the same (or different) as a general
automatic programming system. 



9.  DENDRAL takes the results of a complex interactive event and
tries to deduce what components went into it.  Consider applying the
same techniques to a "de-compiler" which takes machine code and tries
to deduce the higher level language code which produced it.  Pick
your own favorite machine and higher level language, but assume that
the system will have to handle the output of aribtrary compilers (all
correct, but some involving optimizations and other such
complications).  Describe what the resulting system would look like,
in particular pointing out which DENDRAL features seem useful and
which don't.  Reminder: This is a thought problem, NOT a programming
problem -- don't try to build the whole thing, but spend your time
figuring out what the significant issues are. 



10. John Seeley Brown has a paper on "Steps toward automatic theory formation"
3IJCAI p. 121.  It discusses a task involving learning names for kinship
relations.  Describe how Winston's learning program would have to be
modified to handle the learning of Kinship relation names.  Discuss the
problems in designing an appropriate training sequence.  Discuss the
relationship between these and other "concept formation" programs which
might be set the same task.



11. Harry Pople ("On the mechanization of abductive logic" 3IJCAI p. 147)
describes a formalism for abductive reasoning in the context of medical
diagnosis. Describe a production system-based method for doing the reasoning.
How could it be fit into MYCIN?



12. Three papers in 3IJCAI disucss problem solvers in the domain of
moving objects from room to room in a simple floorplan (Siklossy &
Roach, p. 383; Sacerdoti, p. 412; and Siklossi & Dreussi, p. 423. 
Describe the relative advantages and disadvantages of each (in
particular look for things one system advertises doing which would be
difficult or impossible for the others, and analyze why).